import union_find_set.MyUnionFindSet;

import java.lang.reflect.Array;
import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: wangxin
 * Date: 2024-12-27
 * Time: 19:45
 */

public class GraphByMatrix {
    static class Edge{
        public int src;
        public int dest;
        public int weight;

        public Edge(int src, int dest, int weight) {
            this.src = src;
            this.dest = dest;
            this.weight = weight;
        }
    }
    public char[] arrayV;
    public int[][] matrix;
    public boolean isDirect;
    public GraphByMatrix(int size,boolean isDirect){
        this.arrayV = new char[size];
        this.matrix = new int[size][size];
        for(int i = 0;i < matrix.length;i++){
            Arrays.fill(matrix[i], Constant.Max);
        }
        this.isDirect = isDirect;
    }
    public void initArrayV(char[] array){
        for(int i= 0;i < array.length;i++){
            arrayV[i] = array[i];
        }
    }
    public void addEdge(char v1,char v2,int weight){
        int src = findMatrixIndex(v1);
        int dest = findMatrixIndex(v2);
        matrix[src][dest] = weight;
        if(!isDirect){
            matrix[dest][src] = weight;
        }
    }
    public int findMatrixIndex(char v){
        for(int i = 0;i < arrayV.length;i++){
            if(arrayV[i] == v){
                return i;
            }
        }
        return -1;
    }
    public int getDevOfV(char v){
        int indexV = findMatrixIndex(v);
        int count = 0;
        for(int i = 0; i < arrayV.length;i++){
            if(matrix[indexV][i] != Constant.Max){
                count++;
            }
        }
        if(isDirect){
            for(int i = 0; i < arrayV.length;i++){
                if(matrix[i][indexV] != Constant.Max){
                    count++;
                }
            }
        }
        return count;
    }
    public void printGraph(){
        for(int i = 0;i < matrix.length;i++){
            for(int j = 0;j < matrix[i].length;j++){
                if(matrix[i][j] == Constant.Max){
                    System.out.print("∞"+" ");
                }else{
                    System.out.print(matrix[i][j]+" ");
                }
            }
            System.out.println();
        }
    }
    public void bfs(char v){
        boolean[] vis = new boolean[arrayV.length];
        Arrays.fill(vis,false);
        int index = findMatrixIndex(v);
        Queue<Integer> q = new LinkedList<>();
        q.offer(index);

        while(!q.isEmpty()){
            int top = q.poll();
            vis[top] = true;
            System.out.print(arrayV[top]+":"+top+"->");
            for(int i = 0; i < arrayV.length;i++){
                if(matrix[top][i] != Constant.Max&&!vis[i]){
                    q.offer(i);
                    vis[i] = true;
                }
            }
        }
    }
    public void dfs(char v) {
        boolean[] vis = new boolean[arrayV.length];
        Arrays.fill(vis,false);
        int index = findMatrixIndex(v);
        dfsChild(index,vis);
    }

    private void dfsChild(int index, boolean[] vis) {
        vis[index] = true;
        System.out.print(arrayV[index]+":"+index+"->");
        for(int i = 0; i < arrayV.length;i++){
        if(matrix[index][i] != Constant.Max&&!vis[i]){
            dfsChild(i,vis);
        }
        }
    }
    public int kruskal(GraphByMatrix minTree){
        PriorityQueue<Edge> minQ = new PriorityQueue<>(new Comparator<Edge>() {
            @Override
            public int compare(Edge o1, Edge o2) {
                return o1.weight - o2.weight;
            }
        });
        int n = matrix.length;
        for(int i = 0;i < n;i++){
            for (int j = 0;j < n;j++){
                if(i < j&&matrix[i][j] != Constant.Max){
                    minQ.offer(new Edge(i,j,matrix[i][j]));
                }
            }
        }
        int size = 0;
        int totalWeight = 0;
        MyUnionFindSet ufs = new MyUnionFindSet(n);
        while(!minQ.isEmpty()){
            Edge edge = minQ.poll();
           int srcIndex = edge.src;
           int destIndex = edge.dest;
           if(!ufs.isUnionFindSet(srcIndex,destIndex)){
               System.out.println(arrayV[srcIndex] +"-> "
                       +arrayV[destIndex]+" : "+matrix[srcIndex][destIndex]);
               minTree.addEdgeUseIndex(srcIndex,destIndex,matrix[srcIndex][destIndex]);
               ufs.union(srcIndex,destIndex);
               totalWeight += matrix[srcIndex][destIndex];
               size++;
           }
         if(size == n -1){
             return totalWeight;
         }
        }
        return -1;
    }
    public void addEdgeUseIndex(int srcIndex,int destIndex,int weight){
        matrix[srcIndex][destIndex] = weight;
        if(!isDirect){
            matrix[destIndex][srcIndex] = weight;
        }
    }

    public int prim(GraphByMatrix minTree,char chV){
        int n = matrix.length;
        int srcl = findMatrixIndex(chV);
        Set<Integer> setX = new HashSet<>();
        setX.add(srcl);
        Set<Integer> setY = new HashSet<>();
        for(int i = 0;i < n;i++){
            if(i != srcl){
                setY.add(i);
            }
        }
        PriorityQueue<Edge> minQ = new PriorityQueue<>(new Comparator<Edge>() {
            @Override
            public int compare(Edge o1, Edge o2) {
                return o1.weight-o2.weight;
            }
        });
        for(int i = 0;i < n;i++){
            if(matrix[srcl][i] != Constant.Max){
                minQ.offer(new Edge(srcl,i,matrix[srcl][i]));
            }
        }
        int size = 0;
        int totalWeight = 0;
        while (!minQ.isEmpty()){
            Edge min = minQ.poll();
            int srcIndex = min.src;
            int destIndex = min.dest;
            if(setX.contains(destIndex)){
                System.out.println("构成环：");
                System.out.println(arrayV[srcIndex] + "-> "
                        + arrayV[destIndex] + " : " + matrix[srcIndex][destIndex]);
            }else{
                minTree.addEdgeUseIndex(srcIndex,destIndex,matrix[srcIndex][destIndex]);
                System.out.println(arrayV[srcIndex]+"-> "
                        +arrayV[destIndex]+": "+ matrix[srcIndex][destIndex]);
                size++;
                totalWeight += matrix[srcIndex][destIndex];
            }
            if(size == n-1){
                return totalWeight;
            }
            setX.add(destIndex);
            setY.remove(destIndex);
            for(int i = 0;i < n;i++){
                if(matrix[destIndex][i] != Constant.Max&&!setX.contains(i)){
                    minQ.offer(new Edge(destIndex,i,matrix[destIndex][i]));
                }
            }
        }
        return -1;
    }
    public void dijkstra(char vSrc,int[] dist,int[] pPath){
        int srcIndex = findMatrixIndex(vSrc);
        Arrays.fill(dist,Constant.Max);
        Arrays.fill(pPath,-1);
        dist[srcIndex] = 0;
        pPath[srcIndex] = srcIndex;
        int n = arrayV.length;
        boolean[] vis = new boolean[n];
        Arrays.fill(vis,false);
        for(int k = 0;k < n;k++){
            int min = Constant.Max;
            int u = srcIndex;
            for(int i = 0;i < n;i++){
                if(!vis[i]&&min > dist[i]){
                    min = dist[i];
                    u = i;
                }
            }
            vis[u] = true;
            for(int v= 0;v < n;v++){
                if(!vis[v]&&matrix[u][v]!=Constant.Max&&matrix[u][v]+dist[u] < dist[v]){
                    dist[v] = matrix[u][v]+dist[u];
                    pPath[v] = u;
                }
            }
        }
    }
    public void printShortPath(char vSrc,int[] dist,int[] pPath){
        int srcIndex = findMatrixIndex(vSrc);
        int n = arrayV.length;
        for(int i = 0;i < n;i++){
            if(i != srcIndex){
                ArrayList<Integer> path = new ArrayList<>();
                int parentI = i;
                while (parentI != srcIndex&&parentI>=0){
                    path.add(parentI);
                    parentI = pPath[parentI];
                }
                path.add(parentI);
                Collections.reverse(path);
                for(int pos:path){
                    System.out.print(arrayV[pos]+"-> ");
                }
                System.out.println(dist[i]);
            }

        }
    }
    public boolean bellmanFord(char vSrc,int[] dist,int[] pPath){
        int srcIndex = findMatrixIndex(vSrc);
        Arrays.fill(dist,Constant.Max);
        Arrays.fill(pPath,-1);
        dist[srcIndex] = 0;
        int n = arrayV.length;
        for (int k = 0;k < n;k++){
            for(int i = 0;i < n;++i){
                for(int j = 0;j < n;++j){
                    if(matrix[i][j] != Constant.Max&&dist[i] + matrix[i][j] < dist[j]){
                        dist[j] = dist[i] + matrix[i][j];
                        pPath[j] = i;
                    }
                }
            }
        }
        for (int i = 0;i < n;++i){
            for(int j = 0;j < n;++j){
                if(matrix[i][j] != Constant.Max&& dist[i]+matrix[i][j] < dist[j]){
                    return false;
                }
            }
        }
        return true;
    }
    public void floydWarShall(int[][] dist,int[][] pPath){
        int n = arrayV.length;
        for(int i = 0;i < n;i++){
            Arrays.fill(dist[i],Constant.Max);
            Arrays.fill(pPath[i],-1);
        }
        for(int i = 0;i < n;i++){
            for(int j = 0; j < n;j++){
                if(matrix[i][j]!= Constant.Max){
                    dist[i][j] = matrix[i][j];
                    pPath[i][j] = i;
                }else{
                    pPath[i][j] = -1;
                }
                if(i == j){
                    dist[i][j] = 0;
                    pPath[i][j] = -1;
                }
            }
        }
       for(int k = 0;k < n;k++){
           for (int i = 0; i < n; i++) {
               for (int j = 0; j < n; j++) {
                   if(dist[i][k]!=Constant.Max&&dist[k][j] != Constant.Max
                           &&dist[i][k]+dist[k][j] < dist[i][j]){
                       dist[i][j] = dist[i][k]+dist[k][j];
                       pPath[i][j] = pPath[k][j];
                   }
               }
           }
       }
    }
    public static void testGraphFloydWarShall() {
        String str = "12345";
        char[] array = str.toCharArray();
        GraphByMatrix g = new GraphByMatrix(str.length(),true);
        g.initArrayV(array);
        g.addEdge('1', '2', 3);
        g.addEdge('1', '3', 8);
        g.addEdge('1', '5', -4);
        g.addEdge('2', '4', 1);
        g.addEdge('2', '5', 7);
        g.addEdge('3', '2', 4);
        g.addEdge('4', '1', 2);
        g.addEdge('4', '3', -5);
        g.addEdge('5', '4', 6);
        int[][] dist = new int[array.length][array.length];
        int[][] parentPath = new int[array.length][array.length];
        g.floydWarShall(dist,parentPath);
        for (int i = 0; i < array.length; i++) {
            g.printShortPath(array[i],dist[i],parentPath[i]);
        }
    }
    public static void main(String[] args) {
      testGraphFloydWarShall();
    }
    public static void testGraphBellmanFord() {
        String str = "syztx";
        char[] array = str.toCharArray();
        GraphByMatrix g = new GraphByMatrix(str.length(),true);
        g.initArrayV(array);
//        g.addEdge('s', 't', 6);
//        g.addEdge('s', 'y', 7);
//        g.addEdge('y', 'z', 9);
//        g.addEdge('y', 'x', -3);
//        g.addEdge('z', 's', 2);
//        g.addEdge('z', 'x', 7);
//        g.addEdge('t', 'x', 5);
//        g.addEdge('t', 'y', 8);
//        g.addEdge('t', 'z', -4);
//        g.addEdge('x', 't', -2);
        g.addEdge('s', 't', 6);
        g.addEdge('s', 'y', 7);
        g.addEdge('y', 'z', 9);
        g.addEdge('y', 'x', -3);
        g.addEdge('y', 's', 1);
        g.addEdge('z', 's', 2);
        g.addEdge('z', 'x', 7);
        g.addEdge('t', 'x', 5);
        g.addEdge('t', 'y', -8);
        g.addEdge('t', 'z', -4);
        g.addEdge('x', 't', -2);
        int[] dist = new int[array.length];
        int[] parentPath = new int[array.length];
        boolean flg = g.bellmanFord('s', dist, parentPath);
        if(flg) {
            g.printShortPath('s', dist, parentPath);
        }else {
            System.out.println("存在负权回路");
        }
    }

    public static void testGraphDijkstra() {
        String str = "syztx";
        char[] array = str.toCharArray();
        GraphByMatrix g = new GraphByMatrix(str.length(),true);
        g.initArrayV(array);
        g.addEdge('s', 't', 10);
        g.addEdge('s', 'y', 5);
        g.addEdge('y', 't', 3);
        g.addEdge('y', 'x', 9);
        g.addEdge('y', 'z', 2);
        g.addEdge('z', 's', 7);
        g.addEdge('z', 'x', 6);
        g.addEdge('t', 'y', 2);
        g.addEdge('t', 'x', 1);
        g.addEdge('x', 'z', 4);
        int[] dist = new int[array.length];
        int[] parentPath = new int[array.length];
        g.dijkstra('s', dist, parentPath);
        g.printShortPath('s', dist, parentPath);
    }


    public static void testGraphMinTree() {
        String str = "abcdefghi";
        char[] array =str.toCharArray();
        GraphByMatrix g = new GraphByMatrix(str.length(),false);
        g.initArrayV(array);
        g.addEdge('a', 'b', 4);
        g.addEdge('a', 'h', 8);
//g.addEdge('a', 'h', 9);
        g.addEdge('b', 'c', 8);
        g.addEdge('b', 'h', 11);
        g.addEdge('c', 'i', 2);
        g.addEdge('c', 'f', 4);
        g.addEdge('c', 'd', 7);
        g.addEdge('d', 'f', 14);
        g.addEdge('d', 'e', 9);
        g.addEdge('e', 'f', 10);
        g.addEdge('f', 'g', 2);
        g.addEdge('g', 'h', 1);
        g.addEdge('g', 'i', 6);
        g.addEdge('h', 'i', 7);
        GraphByMatrix primTree = new GraphByMatrix(str.length(),false);
        System.out.println(g.prim(primTree,'a'));
        primTree.printGraph();
    }
    public static void testGraphMinTree1() {
        String str = "abcdefghi";
        char[] array =str.toCharArray();
        GraphByMatrix g = new GraphByMatrix(str.length(),false);
        g.initArrayV(array);
        g.addEdgeUseIndex(0, 1, 4);
        g.addEdge('a', 'h', 8);
//g.addEdge('a', 'h', 9);
        g.addEdge('b', 'c', 8);
        g.addEdge('b', 'h', 11);
        g.addEdge('c', 'i', 2);
        g.addEdge('c', 'f', 4);
        g.addEdge('c', 'd', 7);
        g.addEdge('d', 'f', 14);
        g.addEdge('d', 'e', 9);
        g.addEdge('e', 'f', 10);
        g.addEdge('f', 'g', 2);
        g.addEdge('g', 'h', 1);
        g.addEdge('g', 'i', 6);
        g.addEdge('h', 'i', 7);
        GraphByMatrix kminTree = new GraphByMatrix(str.length(),false);
        System.out.println(g.kruskal(kminTree));
        kminTree.printGraph();
    }

    public static void main12(String[] args) {
        testGraphMinTree();
    }
    public static void main1(String[] args) {
        GraphByMatrix graph = new GraphByMatrix(4,false);
        char[] array = {'A','B','C','D'};
        graph.initArrayV(array);
        graph.addEdge('A','B',1);
        graph.addEdge('A','D',1);
        graph.addEdge('B','A',1);
        graph.addEdge('B','C',1);
        graph.addEdge('C','B',1);
        graph.addEdge('C','D',1);
        graph.addEdge('D','A',1);
        graph.addEdge('D','C',1);
//        graph.printGraph();
//        System.out.println(graph.getDevOfV('B'));
        graph.dfs('B');
    }

}
